/*
 * @lc app=leetcode.cn id=146 lang=cpp
 *
 * [146] LRU 缓存机制
 */

// @lc code=start
struct Node {
  int key, val;
  Node *next, *prev;
  Node(int k, int v)
      : key(k)
      , val(v)
      , next(nullptr)
      , prev(nullptr)
  {}
};
class LRUCache
{
public:
  int N;
  int n;
  Node *head, *tail;
  unordered_map<int, Node*> nodes;

  LRUCache(int capacity)
      : N(capacity)
      , n(0)
      , nodes(unordered_map<int, Node*>())
  {
    head = new Node(-1, -1);
    tail = new Node(0, 0);
    head->next = tail;
    tail->prev = head;
  }

  int get(int key)
  {
    auto itr = nodes.find(key);
    if (itr == nodes.end())
      return -1;
    else {
      ToHead(itr->second);
      return itr->second->val;
    }
  }

  void put(int key, int value)
  {
    auto itr = nodes.find(key);
    // key 存在, 更新value
    if (itr != nodes.end()) {
      itr->second->val = value;
      // 将最近访问的key移至链表头部即可
      ToHead(itr->second);
    }
    // key不存在，写入
    else {
      Node* new_node = new Node(key, value);
      if (n < N)// 容量足够
        ++n;
      else {
        Node* del = DelTail();
        nodes.erase(del->key);
        delete del;
      }
      // 链接新节点至head
      Link(new_node, head, head->next);
      // hash table 记录
      nodes[key] = new_node;
    }
  }

  void ToHead(Node* node)
  {
    Abort(node);
    Link(node, head, head->next);
  }

  Node* DelTail()
  {
    Node* tmp = tail->prev;
    Abort(tmp);
    return tmp;
  }

  void Abort(Node* node)
  {
    node->prev->next = node->next;
    node->next->prev = node->prev;
  }

  void Link(Node* m, Node* p, Node* n)
  {
    p->next = m;
    m->prev = p;
    n->prev = m;
    m->next = n;
  }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */
// @lc code=end
